Search results for "Longest path problem"

showing 4 items of 4 documents

The project scheduling polyhedron: Dimension, facets and lifting theorems

1993

Abstract The Project scheduling with resource constraints can be formulated as follows: given a graph G with node set N, a set H of directed arcs corresponding to precedence relations, and a set H′ of disjunctive arcs reflecting the resource incompatibilities, find among the subsets of H′ satisfying the resource constraints the set S that minimizes the longest path in graph (N, H ∪ S). We define the project scheduling polyhedron Qs as the convex hull of the feasible solutions. We investigate several classes of inequalities with respect to their facet-defining properties for the associated polyhedron. The dimension of Qs is calculated and several inequalities are shown to define facets. For …

Convex hullDiscrete mathematicsmedicine.medical_specialtyInformation Systems and ManagementGeneral Computer SciencePolyhedral combinatoricsDimension (graph theory)Graph theoryManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringLongest path problemCombinatoricsPolyhedronRectificationModeling and SimulationmedicineGraph (abstract data type)MathematicsEuropean Journal of Operational Research
researchProduct

The computational complexity of the relative robust shortest path problem with interval data

2004

Abstract The paper deals with the relative robust shortest path problem in a directed arc weighted graph, where arc lengths are specified as intervals containing possible realizations of arc lengths. The complexity status of this problem has been unknown in the literature. We show that the problem is NP -hard.

Discrete mathematicsInformation Systems and ManagementGeneral Computer ScienceManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringLongest path problemWidest path problemEuclidean shortest pathShortest Path Faster AlgorithmTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYModeling and SimulationShortest path problemK shortest path routingCanadian traveller problemDistanceMathematicsofComputing_DISCRETEMATHEMATICSMathematicsEuropean Journal of Operational Research
researchProduct

The Spanning Tree based Approach for Solving the Shortest Path Problem in Social Graphs

2016

Nowadays there are many social media sites with a very large number of users. Users of social media sites and relationships between them can be modelled as a graph. Such graphs can be analysed using methods from social network analysis (SNA). Many measures used in SNA rely on computation of shortest paths between nodes of a graph. There are many shortest path algorithms, but the majority of them suits only for small graphs, or work only with road network graphs that are fundamentally different from social graphs. This paper describes an efficient shortest path searching algorithm suitable for large social graphs. The described algorithm extends the Atlas algorithm. The proposed algorithm so…

Discrete mathematicsta113Mathematical optimizationSpanning treesocial network analysisComputer scienceAtlas algorithm020206 networking & telecommunications02 engineering and technologyLongest path problemverkostoanalyysiWidest path problemOdnoklassnikiEuclidean shortest pathShortest Path Faster Algorithmsocial graph020204 information systemsShortest path problem0202 electrical engineering electronic engineering information engineeringK shortest path routingCanadian traveller problemshortest path problemMathematicsofComputing_DISCRETEMATHEMATICS
researchProduct

Symbolic Worst Case Execution Times

2011

In immediate or hard real-time systems the correctness of an operation depends not only upon its logical correctness, but also on the time in which it is computed. In such systems, it is imperative that operations are performed within a given deadline because missing this deadline constitutes the failure of the complete system. Such systems include medical systems, flight control systems and other systems whose failure in responding punctually results in a high economical loss or even in the loss of human lives. These systems are usually analyzed in a sequence of steps in which first, a socalled control flow graph (CFG) is constructed that represents possible program flows. Furthermore, bou…

PolynomialSequenceCorrectnessWorst-case execution timeComputer scienceCode (cryptography)Control flow graphInteger programmingAlgorithmLongest path problem
researchProduct